SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Control table</title>

</head>

Control table

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

A control table is a <a href="Array_(data_structure)" title="Array (data structure)">array</a> of <a href="Record_(computer_science)" title="Record (computer science)">records</a> used to direct the <a href="Control_flow" title="Control flow">control flow</a> of a <a href="Computer_program" title="Computer program">computer program</a>. <a href="Software" title="Software">Software</a> that uses a control table is said to be table-driven.<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a> A control table encodes both a <a href="Conditional_(programming)" class="mw-redirect" title="Conditional (programming)">conditional expression</a> and a <a href="Function_(computer_programming)" title="Function (computer programming)">function</a> <a href="Reference_(computer_science)" title="Reference (computer science)">reference</a>. An <a href="Interpreter_(computing)" title="Interpreter (computing)">interpreter</a> processes a table by applying input data to the conditional expression and invoking the selected function. Using a control table can reduce the need for repetitive code that implements the same logic. The two-dimensional nature of most tables makes them easier to view and update than the one-dimensional nature of program code.

Typical uses for a control table include:

<ul><li>Transform an input value to an <a href="Associative_array" title="Associative array">index</a>, for branching or <a href="Pointer_(computer_programming)" title="Pointer (computer programming)">pointer</a> <a href="Lookup_table" title="Lookup table">lookup</a></li>

<li>Transform an input value to a program name, relative <a href="Subroutine" class="mw-redirect" title="Subroutine">subroutine</a> number, <a href="Label_(programming_language)" class="mw-redirect" title="Label (programming language)">program label</a> or program <a href="Offset_(computer_science)" title="Offset (computer science)">offset</a>, to alter <a href="Control_flow" title="Control flow">control flow</a></li>

<li>Control a <a href="Main_loop" class="mw-redirect" title="Main loop">main loop</a> in <a href="Event-driven_programming" title="Event-driven programming">event-driven programming</a> using a <a href="Control_variable_(programming)" class="mw-redirect" title="Control variable (programming)">control variable</a> for <a href="State_transition" class="mw-redirect" title="State transition">state transitions</a></li>

<li>Control the program cycle for <a href="Online_transaction_processing" title="Online transaction processing">online transaction processing</a> applications</li></ul>

A relatively advanced use as instructions for a <a href="Virtual_machine" title="Virtual machine">virtual machine</a> processed by an interpreter – similar to <a href="Bytecode" title="Bytecode">bytecode</a> but usually with operations implied by the table structure itself.

<div class="mw-heading mw-heading2"><h2 id="Data_structure">Data structure</h2></div>

A table can be structured in a variety of ways. It may have one or multiple dimensions and be of fixed or <a href="Variable_length_code" class="mw-redirect" title="Variable length code">variable length</a>. The structure of the table may be similar to a <a href="Multimap_(data_structure)" class="mw-redirect" title="Multimap (data structure)">multimap</a> <a href="Associative_array" title="Associative array">associative array</a>, where a data value (or combination of data values) may be mapped to one or more functions to be performed. Often, the structure allows tabular data is <a href="Software_portability" title="Software portability">portable</a> between <a href="Computer_platform" class="mw-redirect" title="Computer platform">computer platforms</a> as long as a compatible interpreter exists on each platform.

<div class="mw-heading mw-heading3"><h3 id="Trival_hash_function">Trival hash function</h3></div>

A relatively simple implementation consists of a <a href="Sparse_file" title="Sparse file">sparse</a>, one-dimensional array of values. The index space is fully covered by the array such that lookup involves indexing into the array by the input value, and a value is found even for an index that is not intended to be used; preventing an error that might otherwise occur for an unused index value. The lookup is achieved in <a href="Constant_time" class="mw-redirect" title="Constant time">constant time</a>; without searching. In most <a href="Computer_architecture" title="Computer architecture">architectures</a>, this can be accomplished in two or three <a href="Machine_instruction" class="mw-redirect" title="Machine instruction">machine instructions</a>. The technique is known as a "<a href="Trivial_hash_function" class="mw-redirect" title="Trivial hash function">trivial hash function</a>" or, when used specifically for branch tables, "<a href="Double_dispatch" title="Double dispatch">double dispatch</a>".

To be feasible, the range of index values should be relatively small. In the example below, the control table is indexed by ASCII value so it has 256 entries; an entry for each ASCII value; omitted entries are shown as '...'. Only the values for the letter A, D, M, and S are important. All other values are uninteresting and set to 0. A two-byte index would require a minimum of 65,536 entries to handle all input possibilities.

</caption>

<th>index (ASCII)</th>

<th>Array

</th></tr>

<tr>

<td style="background:lightblue;">0

</td></tr>

<tr>

<td style="background:lightblue;">0

</td></tr>

<tr>

<td style="background:lightblue;">1

</td></tr>

<tr>

<td style="background:lightblue;">0

</td></tr>

<tr>

<td style="background:lightblue;">4

</td></tr>

<tr>

<td style="background:lightblue;">0

</td></tr>

<tr>

<td style="background:lightblue;">3

</td></tr>

<tr>

<td style="background:lightblue;">0

</td></tr>

<tr>

<td style="background:lightblue;">2

</td></tr>

<tr>

<td style="background:lightblue;">0

</td></tr>

<tr>

<td style="background:lightblue;">0

</td></tr></tbody></table>

In automata-based programming and <a href="Pseudoconversational_transaction" title="Pseudoconversational transaction">pseudoconversational transaction</a> processing, if the number of distinct program states is small, a "dense sequence" control variable can be used to efficiently dictate the entire flow of the main program loop.

<div class="mw-heading mw-heading3"><h3 id="Branch_table">Branch table</h3></div>

A <a href="Branch_table" title="Branch table">branch table</a> is a one-dimensional array of <a href="Machine_code" title="Machine code">machine code</a> <a href="Branch_(computer_science)" title="Branch (computer science)">branch/jump</a> instructions to effect a <a href="Multiway_branch" title="Multiway branch">multiway branch</a> to a program label when branched into by an immediately preceding, and indexed branch. It is sometimes generated by an <a href="Optimizing_compiler" title="Optimizing compiler">optimizing compiler</a> to execute a <a href="Switch_statement" title="Switch statement">switch statement</a> – provided that the input range is small and dense, with few gaps.<a href="#cite_note-3">[3]</a> (as created by the previous array example)

Although quite compact – compared to the multiple equivalent <code>If</code> statements – the branch instructions still carry some redundancy, since the branch <a href="Opcode" title="Opcode">opcode</a> and condition code mask are repeated alongside the branch offsets. Control tables containing only the offsets to the program labels can be constructed to overcome this redundancy (at least in assembly languages) and yet requiring only minor execution time <a href="Computational_overhead" class="mw-redirect" title="Computational overhead">overhead</a> compared to a conventional branch table.

<div class="mw-heading mw-heading3"><h3 id="Decision_table">Decision table</h3></div>

Often, a control table is a <a href="Truth_table" title="Truth table">truth table</a> or an implementation of a <a href="Decision_table" title="Decision table">decision table</a> or a <a href="Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">tree</a> of decision tables. The tables contains (often implied) <a href="Propositional_formula" title="Propositional formula">propositions</a>, together with one or more associated actions. The actions are usually performed by generic or custom-built <a href="Subroutine" class="mw-redirect" title="Subroutine">subroutines</a> that are called by an interpreter. The interpreter, a <a href="Virtual_machine" title="Virtual machine">virtual machine</a>, executes the control table entries and thus provides a higher level of <a href="Abstraction_(computer_science)" title="Abstraction (computer science)">abstraction</a> than the interpreter.

A control table can act like a <a href="Switch_statement" title="Switch statement">switch statement</a> or more generally as a nested <a href="If-then-else" class="mw-redirect" title="If-then-else">if-then-else</a> construct that includes <a href="Logical_predicate" class="mw-redirect" title="Logical predicate">logical predicates</a> (using <a href="Boolean_algebra_(logic)" class="mw-redirect" title="Boolean algebra (logic)">boolean</a> style <a href="Logical_conjunction" title="Logical conjunction">AND</a>/<a href="Logical_disjunction" title="Logical disjunction">OR</a> conditions) for each case. Such as control table provides for a language-independent implementation of what otherwise is a language-dependent construct. The table embodies the <a href="Essence" title="Essence">essence</a> of a program; stripped of programming language syntax and platform dependent aspects; condensed to data and implied logic. The meaning of the table includes implied operations instead of being explicit as in a more typical a <a href="Programming_paradigm" title="Programming paradigm">programming paradigm</a>.

Typically, a two-dimensional control table contains value/action pairs and may additionally contain operators and <a href="Type_system" title="Type system">type</a> information such as the location, size and format of input or output data, whether <a href="Data_conversion" title="Data conversion">data conversion</a> is required. The table may contain <a href="Array_index" class="mw-redirect" title="Array index">indexes</a> or relative or absolute <a href="Pointer_(computer_programming)" title="Pointer (computer programming)">pointers</a> to generic or customized primitives or <a href="Subroutine" class="mw-redirect" title="Subroutine">subroutines</a> to be executed depending upon other values in the row.

The table below is a prototype of a control table that implies an action based on a single input value.

</caption>

<th>(implied) IF =</th>

<th>(implied) perform

</th></tr>

<tr>

<td>value</td>

<td>action

</td></tr>

<tr>

<td>value</td>

<td>action

</td></tr></tbody></table>

The type of values used to in a control table depends on the <a href="Computer_language" title="Computer language">computer language</a> used for the interpreter. <a href="Assembly_language" title="Assembly language">Assembly language</a> provides the widest scope for <a href="Data_types" class="mw-redirect" title="Data types">data types</a> including <a href="Machine_code" title="Machine code">machine code</a> for lookup values. Typically, a control table contains values for each possible matching class of input together with a corresponding pointer to an action subroutine. For a language without <a href="Pointer_(computer_programming)" title="Pointer (computer programming)">pointer</a> support, the table can encode an index which can imply an offset value that can be used to accomplish the same as a pointer.

<div class="mw-heading mw-heading2"><h2 id="Storage">Storage</h2></div>

A control table can be stored a variety of ways. It can be stored as part of a program; for example as a <a href="Static_variable" title="Static variable">static variable</a>. It can stored in the <a href="File_system" title="File system">file system</a>; for example as <a href="Flat_file" class="mw-redirect" title="Flat file">flat file</a> or in a <a href="Database" title="Database">database</a>. It can be built dynamically by the program. For efficiency, the table should be resident in program memory when the interpreter uses it.

<div class="mw-heading mw-heading2"><h2 id="The_interpreter_and_subroutines">The interpreter and subroutines</h2></div>

The interpreter can be written in any suitable programming language including a <a href="High_level_language" class="mw-redirect" title="High level language">high level language</a>. A suitably designed <a href="Generic_programming" title="Generic programming">generic</a> interpreter, together with a well chosen set of generic subroutines (able to process the most commonly occurring primitives), would require additional conventional coding only for new custom subroutines (in addition to specifying the control table itself). The interpreter, optionally, may only apply to some well-defined sections of a complete application program (such as the <a href="Main_loop" class="mw-redirect" title="Main loop">main control loop</a>) and not other, 'less conditional', sections (such as program initialization, termination and so on).

The interpreter does not need to be unduly complex, or produced by a programmer with the advanced knowledge of a compiler writer, and can be written just as any other application program – except that it is usually designed with efficiency in mind. Its primary function is to "execute" the table entries as a set of "instructions". There need be no requirement for parsing of control table entries and these should therefore be designed, as far as possible, to be 'execution ready', requiring only the "plugging in" of variables from the appropriate columns to the already compiled generic code of the interpreter. The <a href="Instruction_(computer_science)" class="mw-redirect" title="Instruction (computer science)">program instructions</a> are, in theory, infinitely <a href="Extensible" class="mw-redirect" title="Extensible">extensible</a> and constitute (possibly arbitrary) values within the table that are meaningful only to the interpreter. The <a href="Control_flow" title="Control flow">control flow</a> of the interpreter is normally by sequential processing of each table row but may be modified by specific actions in the table entries.

These arbitrary values can thus be designed with <a href="Algorithmic_efficiency" title="Algorithmic efficiency">efficiency</a> in mind – by selecting values that can be used as direct indexes to data or <a href="Function_pointers" class="mw-redirect" title="Function pointers">function pointers</a>. For particular platforms/<a href="Computer_language" title="Computer language">language</a>, they can be specifically designed to minimize <a href="Instruction_path_length" title="Instruction path length">instruction path lengths</a> using <a href="Branch_table" title="Branch table">branch table</a> values or even, in some cases such as in <a href="Just-in-time_compilation" title="Just-in-time compilation">JIT</a> compilers, consist of directly executable <a href="Machine_code" title="Machine code">machine code</a> "<a href="Snippet_(programming)" title="Snippet (programming)">snippets</a>" (or pointers to them).

The subroutines may be coded either in the same language as the interpreter itself or any other supported program language (provided that suitable inter-language 'Call' linkage mechanisms exist). The choice of language for the interpreter and/or subroutines will usually depend upon how portable it needs to be across various <a href="Platform_(computing)" class="mw-redirect" title="Platform (computing)">platforms</a>. There may be several versions of the interpreter to enhance the <a href="Porting" title="Porting">portability</a> of a control table. A subordinate control table pointer may optionally substitute for a subroutine pointer in the 'action' columns if the interpreter supports this construct, representing a conditional 'drop' to a lower logical level, mimicking a conventional <a href="Structured_programming" title="Structured programming">structured program</a> structure.

<div class="mw-heading mw-heading2"><h2 id="Performance_considerations">Performance considerations</h2></div>

At first sight, the use of control tables would appear to add quite a lot to a program's <a href="Computational_overhead" class="mw-redirect" title="Computational overhead">overhead</a>, requiring, as it does, an interpreter process before the 'native' programming language statements are executed. This however is not always the case. By separating (or 'encapsulating') the executable coding from the logic, as expressed in the table, it can be more readily targeted to perform its function most efficiently. This may be experienced most obviously in a <a href="Spreadsheet" title="Spreadsheet">spreadsheet</a> application – where the underlying spreadsheet software transparently converts complex logical 'formulae' in the most efficient manner it is able, in order to display its results.

The examples below have been chosen partly to illustrate potential performance gains that may not only compensate significantly for the additional tier of abstraction, but also improve upon – what otherwise might have been – less efficient, less maintainable and lengthier code. Although the examples given are for a 'low level' assembly language and for the <a href="C_(language)" class="mw-redirect" title="C (language)">C language</a>, it can be seen, in both cases, that very few lines of code are required to implement the control table approach and yet can achieve very significant <a href="Constant_time" class="mw-redirect" title="Constant time">constant time</a> performance improvements, reduce repetitive source coding and aid clarity, as compared with <a href="Verbose" class="mw-redirect" title="Verbose">verbose</a> conventional program language constructs. See also the <a class="mw-selflink-fragment" href="#Quotations">quotations</a> by <a href="Donald_Knuth" title="Donald Knuth">Donald Knuth</a>, concerning tables and the efficiency of <a href="Multiway_branch" title="Multiway branch">multiway branching</a> in this article.

<div class="mw-heading mw-heading2"><h2 id="Examples_of_control_tables">Examples of control tables</h2></div>

The following examples are <a href="Arbitrary" class="mw-redirect" title="Arbitrary">arbitrary</a> (and based upon just a single input for simplicity), however the intention is merely to demonstrate how control flow can be effected via the use of tables instead of regular program statements. It should be clear that this technique can easily be extended to deal with multiple inputs, either by increasing the number of columns or utilizing multiple table entries (with optional and/or operator). Similarly, by using (hierarchical) 'linked' control tables, <a href="Structured_programming" title="Structured programming">structured programming</a> can be accomplished (optionally using indentation to help highlight subordinate control tables).

"CT1" is an example of a control table that is a simple <a href="Lookup_table" title="Lookup table">lookup table</a>. The first column represents the input value to be tested (by an implied 'IF input1 = x') and, if TRUE, the corresponding 2nd column (the 'action') contains a subroutine address to perform by a <a href="System_call" title="System call">call</a> (or <a href="Goto" title="Goto">jump</a> to – similar to a <a href="Switch_statement" title="Switch statement">SWITCH</a> statement). It is, in effect, a <a href="Multiway_branch" title="Multiway branch">multiway branch</a> with return (a form of "<a href="Dynamic_dispatch" title="Dynamic dispatch">dynamic dispatch</a>"). The last entry is the default case where no match is found.

<caption>CT1

</caption>

<th>input 1</th>

<th><a href="Pointer_(computer_programming)" title="Pointer (computer programming)">pointer</a>

</th></tr>

<tr>

/* start https://en.wikipedia.org/ */

.mw-parser-output .monospaced{font-family:monospace,monospace}

/* end https://en.wikipedia.org/ */

</style>A</td>

<td>Add

</td></tr>

<tr>

<td>Subtract

</td></tr>

<tr>

<td>Multiply

</td></tr>

<tr>

<td>Divide

</td></tr>

<tr>

<td>Default

</td></tr></tbody></table></dd></dl>

For programming languages that support pointers within <a href="Data_structure" title="Data structure">data structures</a> alongside other data values, the above table (CT1) can be used to direct <a href="Control_flow" title="Control flow">control flow</a> to an appropriate <a href="Subroutine" class="mw-redirect" title="Subroutine">subroutines</a> according to matching value from the table (without a column to indicate otherwise, equality is assumed in this simple case).

<div class="mw-heading mw-heading3"><h3 id="Assembly_language">Assembly language</h3></div>

No attempt is made to optimize the lookup in coding for this first example (for <a href="IBM/360" class="mw-redirect" title="IBM/360">IBM/360</a> maximum 16Mb address range or <a href="Z/Architecture" title="Z/Architecture">Z/Architecture</a>), and it uses instead a simple <a href="Linear_search" title="Linear search">linear search</a> technique – purely to illustrate the concept and demonstrate fewer source lines. To handle all 256 different input values, approximately 265 lines of source code would be required (mainly single line table entries) whereas multiple 'compare and branch' would have normally required around 512 source lines (the size of the <a href="Binary_file" title="Binary file">binary</a> is also approximately halved, each table entry requiring only 4 bytes instead of approximately 8 bytes for a series of 'compare immediate'/branch instructions (For larger input variables, the saving is even greater).

<pre> * ------------------ interpreter --------------------------------------------*

LM R14,R0,=A(4,CT1,N) Set R14=4, R15 --> table, and R0 =no. of entries in table (N)

TRY CLC INPUT1,0(R15) ********* Found value in table entry ?

BE ACTION * loop * YES, Load register pointer to sub-routine from table

AR R15,R14 * * NO, Point to next entry in CT1 by adding R14 (=4)

BCT R0,TRY ********* Back until count exhausted, then drop through

. default action ... none of the values in table match, do something else

LA R15,4(R15) point to default entry (beyond table end)

ACTION L R15,0(R15) get pointer into R15,from where R15 points

BALR R14,R15 Perform the sub-routine ("CALL" and return)

B END go terminate this program

* ------------------ control table -----------------------------------------*

* | this column of allowable EBCDIC or ASCII values is tested '=' against variable 'input1'

* | | this column is the 3-byte address of the appropriate subroutine

* v v

CT1 DC C'A',AL3(ADD) START of Control Table (4 byte entry length)

DC C'S',AL3(SUBTRACT)

DC C'M',AL3(MULTIPLY)

DC C'D',AL3(DIVIDE)

N EQU (*-CT1)/4 number of valid entries in table (total length / entry length)

DC C'?',AL3(DEFAULT) default entry – used on drop through to catch all

INPUT1 DS C input variable is in this variable

* ------------------ sub-routines ------------------------------------------*

ADD CSECT sub-routine #1 (shown as separate CSECT here but might

. alternatively be in-line code)

. instruction(s) to add

BR R14 return

SUBTRACT CSECT sub-routine #2

. instruction(s) to subtract

BR R14 return

. etc..

</pre>

improving the performance of the interpreter in above example

<dl><dd>To make a selection in the example above, the average <a href="Instruction_path_length" title="Instruction path length">instruction path length</a> (excluding the subroutine code) is '4n/2 +3', but can easily be reduced, where n = 1 to 64, to a <a href="Linear_time" class="mw-redirect" title="Linear time">constant time</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)\,}</annotation>

</semantics>

</math><img src="./0fb3142d0d9658073a488c397897935724062694.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.132ex; height:2.843ex;" alt="{\displaystyle O(1)\,}" loading="lazy"> with a path length of '5' with zero comparisons, if a 256 byte translate table is first utilized to create a direct index to CT1 from the raw EBCDIC data. Where n = 6, this would then be equivalent to just 3 sequential compare & branch instructions. However, where n<=64, on average it would need approximately 13 times less instructions than using multiple compares. Where n=1 to 256, on average it would use approximately 42 times less instructions – since, in this case, one additional instruction would be required (to multiply the index by 4).</dd></dl>

Improved interpreter (up to 26 times less executed instructions than the above example on average, where n= 1 to 64 and up to 13 times less than would be needed using multiple comparisons).

To handle 64 different input values, approximately 85 lines of source code (or less) are required (mainly single line table entries) whereas multiple 'compare and branch' would require around 128 lines (the size of the <a href="Binary_file" title="Binary file">binary</a> is also almost halved – despite the additional 256 byte table required to extract the 2nd index).

<pre> * ------------------ interpreter --------------------------------------------*

SR R14,R14 ********* Set R14=0

CALC IC R14,INPUT1 * calc * put EBCDIC byte into lo order bits (24–31) of R14

IC R14,CT1X(R14) * * use EBCDIC value as index on table 'CT1X' to get new index

FOUND L R15,CT1(R14) ********* get pointer to subroutine using index (0,4, 8 etc.)

BALR R14,R15 Perform the sub-routine ("CALL" and return or Default)

B END go terminate this program

* --------------- additional translate table (EBCDIC --> pointer table INDEX) 256 bytes----*

CT1X DC 12AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) 12 identical sets of 16 bytes of x'00

* representing X'00 – x'BF'

DC AL1(00,04,00,00,16,00,00,00,00,00,00,00,00,00,00,00) ..x'C0' – X'CF'

DC AL1(00,00,00,00,12,00,00,00,00,00,00,00,00,00,00,00) ..x'D0' – X'DF'

DC AL1(00,00,08,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'E0' – X'EF'

DC AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'F0' – X'FF'

* the assembler can be used to automatically calculate the index values and make the values more user friendly

* (for e.g. '04' could be replaced with the symbolic expression 'PADD-CT1' in table CT1X above)

* modified CT1 (added a default action when index = 00, single dimension, full 31 bit address)

CT1 DC A(DEFAULT) index =00 START of Control Table (4 byte address constants)

PADD DC A(ADD) =04

PSUB DC A(SUBTRACT) =08

PMUL DC A(MULTIPLY) =12

PDIV DC A(DIVIDE) =16

* the rest of the code remains the same as first example

</pre>

Further improved interpreter (up to 21 times less executed instructions (where n>=64) than the first example on average and up to 42 times less than would be needed using multiple comparisons).

To handle 256 different input values, approximately 280 lines of source code or less, would be required (mainly single line table entries), whereas multiple 'compare and branch' would require around 512 lines (the size of the <a href="Binary_file" title="Binary file">binary</a> is also almost halved once more).

<pre> * ------------------ interpreter --------------------------------------------*

SR R14,R14 ********* Set R14=0

CALC IC R14,INPUT1 * calc * put EBCDIC byte into lo order bits (24–31) of R14

IC R14,CT1X(R14) * * use EBCDIC value as index on table 'CT1X' to get new index

SLL R14,2 * * multiply index by 4 (additional instruction)

FOUND L R15,CT1(R14) ********* get pointer to subroutine using index (0,4, 8 etc.)

BALR R14,R15 Perform the sub-routine ("CALL" and return or Default)

B END go terminate this program

* --------------- additional translate table (EBCDIC --> pointer table INDEX) 256 bytes----*

CT1X DC 12AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) 12 identical sets of 16 bytes of x'00'

* representing X'00 – x'BF'

DC AL1(00,01,00,00,04,00,00,00,00,00,00,00,00,00,00,00) ..x'C0' – X'CF'

DC AL1(00,00,00,00,03,00,00,00,00,00,00,00,00,00,00,00) ..x'D0' – X'DF'

DC AL1(00,00,02,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'E0' – X'EF'

DC AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'F0' – X'FF'

* the assembler can be used to automatically calculate the index values and make the values more user friendly

* (for e.g. '01' could be replaced with the symbolic expression 'PADD-CT1/4' in table CT1X above)

* modified CT1 (index now based on 0,1,2,3,4 not 0,4,8,12,16 to allow all 256 variations)

CT1 DC A(DEFAULT) index =00 START of Control Table (4 byte address constants)

PADD DC A(ADD) =01

PSUB DC A(SUBTRACT) =02

PMUL DC A(MULTIPLY) =03

PDIV DC A(DIVIDE) =04

* the rest of the code remains the same as the 2nd example

</pre>

<div class="mw-heading mw-heading3"><h3 id="C_language">C language</h3></div>

This example in <a href="C_(programming_language)" title="C (programming language)">C</a> uses two tables, the first (CT1) is a simple <a href="Linear_search" title="Linear search">linear search</a> one-dimensional lookup table – to obtain an index by matching the input (x), and the second, associated table (CT1p), is a table of addresses of labels to jump to.

<div style="font-size: 90%;" class="mw-highlight mw-highlight-lang-c mw-content-ltr mw-highlight-lines" dir="ltr"><pre> static const char CT1[] = { "A", "S", "M", "D" }; /* permitted input values */

static const void *CT1p[] = { &&Add, &&Subtract, &&Multiply, &&Divide, &&Default}; /* labels to goto & default*/

for (int i = 0; i < sizeof(CT1); i++) { /* loop thru ASCII values */

if (x==CT1[i]) goto *CT1p[i]; /* found --> appropriate label */

}

goto *CT1p[i+1]; /* not found --> default label */

</pre></div>

This can be made more efficient if a 256 byte table is used to translate the raw ASCII value (x) directly to a dense sequential index value for use in directly locating the branch address from CT1p (i.e. "<a href="Index_mapping" title="Index mapping">index mapping</a>" with a byte-wide array). It will then execute in <a href="Constant_time" class="mw-redirect" title="Constant time">constant time</a> for all possible values of x (If CT1p contained the names of functions instead of labels, the jump could be replaced with a dynamic function call, eliminating the switch-like goto – but decreasing performance by the additional cost of function <a href="Housekeeping_(computing)" title="Housekeeping (computing)">housekeeping</a>).

<div style="font-size: 80%;" class="mw-highlight mw-highlight-lang-c mw-content-ltr mw-highlight-lines" dir="ltr"><pre> static const void *CT1p[] = {&&Default, &&Add, &&Subtract, &&Multiply, &&Divide};

/* the 256 byte table, below, holds values (1,2,3,4), in corresponding ASCII positions (A,S,M,D), all others set to 0x00 */

static const char CT1x[]={

'\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',

'\x00', '\x01', '\x00', '\x00', '\x04', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x03', '\x00', '\x00',

'\x00', '\x00', '\x00', '\x02', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',

'\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',

'\x00', '\x00', '\x00', '\x00', '\x03', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',

'\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',

'\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00'};

/* the following code will execute in constant time, irrespective of the value of the input character (x) */

i = CT1x(x); /* extract the correct subroutine index from table CT1x using its ASCII value as an index initially */

goto *CT1p[i]; /* goto (Switch to) the label corresponding to the index (0=default, 1=Add, 2=Subtract,.) - see CT1p */

</pre></div>

The next example below illustrates how a similar effect can be achieved in languages that do not support pointer definitions in data structures but do support indexed branching to a subroutine – contained within a (<a href="Zero-based_numbering" title="Zero-based numbering">0-based</a>) array of subroutine pointers. The table (CT2) is used to extract the index (from 2nd column) to the pointer array (CT2P). If pointer arrays are not supported, a SWITCH statement or equivalent can be used to alter the control flow to one of a sequence of program labels (e.g.: case0, case1, case2, case3, case4) which then either process the input directly, or else perform a call (with return) to the appropriate subroutine (default, Add, Subtract, Multiply or Divide,..) to deal with it.

<caption>CT2

</caption>

<th>input 1</th>

<th>subr #

</th></tr>

<tr>

<td>1

</td></tr>

<tr>

<td>2

</td></tr>

<tr>

<td>3

</td></tr>

<tr>

<td>4

</td></tr>

<tr>

<td>0

</td></tr></tbody></table></dd></dl>

As in above examples, it is possible to very efficiently translate the potential <a href="ASCII" title="ASCII">ASCII</a> input values (A,S,M,D or unknown) into a pointer array index without actually using a table lookup, but is shown here as a table for consistency with the first example.

/* start https://en.wikipedia.org/ */

.mw-parser-output .nobold{font-weight:normal}

/* end https://en.wikipedia.org/ */

</style>pointer array

</caption>

<th><a href="Pointer_(computer_programming)" title="Pointer (computer programming)">pointer</a> <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array</a>

</th></tr>

<tr>

<td>default

</td></tr>

<tr>

<td>Add

</td></tr>

<tr>

<td>Subtract

</td></tr>

<tr>

<td>Multiply

</td></tr>

<tr>

<td>Divide

</td></tr>

<tr>

<td>?other

</td></tr></tbody></table></dd></dl>

Multi-dimensional control tables can be constructed (i.e. customized) that can be 'more complex' than the above examples that might test for multiple conditions on multiple inputs or perform more than one 'action', based on some matching criteria. An 'action' can include a pointer to another subordinate control table. The simple example below has had an implicit 'OR' condition incorporated as an extra column (to handle lower case input, however in this instance, this could equally have been handled simply by having an extra entry for each of the lower case characters specifying the same subroutine identifier as the upper case characters). An extra column to count the actual run-time events for each input as they occur is also included.

<caption>CT3

</caption>

<th>input 1</th>

<th>alternate</th>

<th>count

</th></tr>

<tr>

<td>0

</td></tr>

<tr>

<td>0

</td></tr>

<tr>

<td>0

</td></tr>

<tr>

<td>0

</td></tr>

<tr>

<td>0

</td></tr></tbody></table></dd></dl>

The control table entries are then much more similar to conditional statements in <a href="Procedural_language" class="mw-redirect" title="Procedural language">procedural languages</a> but, crucially, without the actual (language dependent) conditional statements (i.e. instructions) being present (the generic code is physically in the interpreter that processes the table entries, not in the table itself – which simply embodies the program logic via its structure and values).

In tables such as these, where a series of similar table entries defines the entire logic, a table entry number or pointer may effectively take the place of a <a href="Program_counter" title="Program counter">program counter</a> in more conventional programs and may be reset in an 'action', also specified in the table entry. The example below (CT4) shows how extending the earlier table, to include a 'next' entry (and/or including an 'alter flow' (<a href="Branch_(computer_science)" title="Branch (computer science)">jump</a>) subroutine) can create a <a href="Program_loop" class="mw-redirect" title="Program loop">loop</a> (This example is actually not the most efficient way to construct such a control table but, by demonstrating a gradual 'evolution' from the first examples above, shows how additional columns can be used to modify behaviour.) The fifth column demonstrates that more than one action can be initiated with a single table entry – in this case an action to be performed after the normal processing of each entry ('-' values mean 'no conditions' or 'no action').

<a href="Structured_programming" title="Structured programming">Structured programming</a> or <a href="Structured_programming" title="Structured programming">"Goto-less" code</a>, (incorporating the equivalent of '<a href="Do_while_loop" title="Do while loop">DO WHILE</a>' or '<a href="For_loop" title="For loop">for loop</a>' constructs), can also be accommodated with suitably designed and 'indented' control table structures.

<table>

<td>

<caption>CT4 (a complete 'program' to read input1 and process, repeating until 'E' encountered)

</caption>

<th>input 1</th>

<th>alternate</th>

<th>count</th>

<th>jump

</th></tr>

<tr>